Search for: All records

This paper reconsiders the On-Demand Multimodal Transit Systems (ODMTS) Design with Adoptions problem (ODMTS-DA) to capture the latent demand in on-demand multimodal transit systems. The ODMTS-DA is a bilevel optimization problem, for which Basciftci and Van Hentenryck proposed an exact combinatorial Benders decomposition. Unfortunately, their proposed algorithm only finds high-quality solutions for medium-sized cities and is not practical for large metropolitan areas. The main contribution of this paper is to propose a new path-based optimization model, called P-Path, to address these computational difficulties. The key idea underlying P-Path is to enumerate two specific sets of paths which capture the essence of the choice model associated with the adoption behavior of riders. With the help of these path sets, the ODMTS-DA can be formulated as a single-level mixed-integer programming model. In addition, the paper presents preprocessing techniques that can reduce the size of the model significantly. P-Path is evaluated on two comprehensive case studies: the midsize transit system of the Ann Arbor – Ypsilanti region in Michigan (which was studied by Basciftci and Van Hentenryck) and the large-scale transit system for the city of Atlanta. The experimental results show that P-Path solves the Michigan ODMTS-DA instances in a few minutes, bringing more than two orders of magnitude improvements compared with the existing approach. For Atlanta, the results show that P-Path can solve large-scale ODMTS-DA instances (about 17 millions variables and 37 millions constraints) optimally in a few hours or in a few days. These results show the tremendous computational benefits of P-Path which provides a scalable approach to the design of on-demand multimodal transit systems with latent demand. History: Accepted by Andrea Lodi, Design & Analysis of Algorithms—Discrete. Funding: This work was partially supported by National Science Foundation Leap-HI [Grant 1854684] and the Tier 1 University Transportation Center (UTC): Transit - Serving Communities Optimally, Responsively, and Efficiently (T-SCORE) from the U.S. Department of Transportation [69A3552047141]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0014 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0014 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 

A classic multi-period stochastic energy system expansion planning (ESEP) model aims to address demand uncertainty by requiring immediate demand satisfaction for all scenarios. However, this approach may result in an expensive system that deviates from the planner’s long-term goals, especially when facing unexpectedly high demand scenarios. To address this issue, we propose a chance-constrained stochastic multi-stage ESEP model that allows for a portion of demand to remain unmet in specific periods while still ensuring complete demand satisfaction during most of the planning horizon, including the final period. This approach provides more time flexibility to build infrastructure and assess needs, ultimately reducing costs and allowing for a broader view of infrastructure planning options. To solve the chance-constrained stochastic model, we introduce a binary- search-based progressive hedging algorithm heuristic, which is particularly useful for large-scale models. We demonstrate the effectiveness and benefits of implementing the chance-constrained model through a case study of Rwanda using real-world data. 

This paper studies how to integrate rider mode preferences into the design of on-demand multimodal transit systems (ODMTSs). It is motivated by a common worry in transit agencies that an ODMTS may be poorly designed if the latent demand, that is, new riders adopting the system, is not captured. This paper proposes a bilevel optimization model to address this challenge, in which the leader problem determines the ODMTS design, and the follower problems identify the most cost efficient and convenient route for riders under the chosen design. The leader model contains a choice model for every potential rider that determines whether the rider adopts the ODMTS given her proposed route. To solve the bilevel optimization model, the paper proposes an exact decomposition method that includes Benders optimal cuts and no-good cuts to ensure the consistency of the rider choices in the leader and follower problems. Moreover, to improve computational efficiency, the paper proposes upper and lower bounds on trip durations for the follower problems, valid inequalities that strengthen the no-good cuts, and approaches to reduce the problem size with problem-specific preprocessing techniques. The proposed method is validated using an extensive computational study on a real data set from the Ann Arbor Area Transportation Authority, the transit agency for the broader Ann Arbor and Ypsilanti region in Michigan. The study considers the impact of a number of factors, including the price of on-demand shuttles, the number of hubs, and access to transit systems criteria. The designed ODMTSs feature high adoption rates and significantly shorter trip durations compared with the existing transit system and highlight the benefits of ensuring access for low-income riders. Finally, the computational study demonstrates the efficiency of the decomposition method for the case study and the benefits of computational enhancements that improve the baseline method by several orders of magnitude. Funding: This research was partly supported by National Science Foundation [Leap HI Proposal NSF-1854684] and the Department of Energy [Research Award 7F-30154].